package com.problem;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/next-permutation/
 */
public class NextPermutation {

    //            1,2,3 → 1,3,2
//            3,2,1 → 1,2,3
//            1,1,5 → 1,5,1
    public void nextPermutation(int[] nums) {
        for (int num : nums) {
            System.out.print(num+" ");
        }
        System.out.println();
        if (nums.length == 1) {
            return;
        }
        if (nums.length ==2) {
            swap(nums,0,1);
            return;
        }
        if (nums.length == 3) {
            if (nums[0] >= nums[1] && nums[1] >= nums[2]) {//321 322  331 333
                Arrays.sort(nums);
            } else if (nums[0] < nums[1] && nums[1] < nums[2]) {//123
                swap(nums,1,2);
            } else if (nums[0]<nums[1] && nums[1]==nums[2]){//122
                swap(nums,0,1);
            } else if (nums[0] == nums[1] && nums[1] < nums[2]) {//112
                swap(nums,1,2);
            } else if (nums[0] > nums[1] && nums[1] < nums[2]) {//312
                swap(nums,1,2);
            } else if (nums[0] < nums[1] && nums[1] > nums[2]) {//132
                swap(nums,0,2);
            }
            return;
        }
        boolean isSort = true;
        for (int i=0;i<nums.length-1;i++) {
            if (nums[i] >= nums[i + 1]) {//996543220...
            } else {
                isSort = false;
                break;
            }
        }
        if (isSort) {
            Arrays.sort(nums);
            return;
        }

        for (int i=nums.length-2;i>0;i--) {
            int minIdx = -1;
            for (int j = i+1;j<nums.length;j++) {
                if (nums[j] > nums[i] && (j+1)>=nums.length) {
                    swap(nums,i,j);
                    return;
                }
                if (nums[j]>nums[i]) {
                    if (minIdx == -1 || nums[minIdx]>nums[j]) {
                        minIdx = j;
                    }
                }
            }
            if (minIdx !=-1) {
                swap(nums,i,minIdx);
                break;
            }
        }
//        for (int num : nums) {
//            System.out.print(num+" ");
//        }
    }

    private void swap(int[] nums,int i, int j) {
        nums[i] += nums[j];
        nums[j] = nums[i]-nums[j];
        nums[i] = nums[i]-nums[j];
    }
}
